package 双指针.三数之和;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
 * 题目描述
 * 题目：给你一个整数数组 nums，要找出 所有和为 0 的三元组 nums[i] + nums[j] + nums[k] == 0，要求：
 * 三个下标不同
 * 结果里不能有重复的三元组（顺序不重要，[-1,0,1] 和 [0,-1,1] 视为同一个）
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 解释：
 * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 * 注意，输出的顺序和三元组的顺序并不重要。
 * 力扣：https://leetcode-cn.com/problems/3sum/
 * 力扣第15题
 * */
/**
 * 题目思路：
 * 排序+固定一位+双指针
 * 先排序数组
 * 外层 for 循环固定一个数 nums[i]，把问题变成「在 i 右边找两个数，使得它们的和是 -nums[i]」
 * 在 [i+1, end] 区间上，用 双指针 做「两数之和」：
 * 左指针 lo = i+1
 * 右指针 hi = n-1
 * 如果 nums[lo] + nums[hi] == -nums[i] → 找到一组
 * 小于目标 → 左指针右移（和变大）
 * 大于目标 → 右指针左移（和变小）
 * 注意：
 * 对于同一个 i，如果 nums[i] 和前一个相同，就跳过
 * 找到一个三元组后，lo 和 hi 也要跳过重复的值
 * */
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); // 双指针吗，小了左移，大了右移
        List<List<Integer>> res = new LinkedList<>(); // 用list存结果，每个结果本身又是一个List<Integer>
        for(int i = 0;i < nums.length - 2;i++){
            // 如果当前数是正数，后面的数大于等于它，相加不可能等于0
            if(nums[i] > 0){
                break;
            }
            // 跳过当前数组中重复的元素
            // 同一个值，只让他当一次第一个数
            if(i == 0 || (i > 0 && nums[i] != nums[i - 1])){
                int lo = i + 1;
                int hi = nums.length - 1;
                int sum = -nums[i];
                // 开始两数之和的双指针搜索
                while(lo < hi){
                    if(nums[lo] + nums[hi] == sum){
                        // 找到一主解
                        res.add(Arrays.asList(nums[i],nums[lo],nums[hi]));
                        // 跳过重复的lo和hi的值
                        while(lo < hi && nums[lo] == nums[lo + 1]){
                            lo++;
                        }
                        while(lo < hi && nums[hi] == nums[hi - 1]){
                            hi--;
                        }
                        lo++;
                        hi--;
                    }else if(nums[lo] + nums[hi] < sum){
                        // 需要让和变大，左指针右移（因为是升序的）
                        lo++;
                    }else{
                        // 需要让和变小，右指针左移
                        hi--;
                    }
                }
            }
        }
        return res;
    }
}